package com.gitee.wsl.collections.queue

/**
 * FIFO queue
 *
 * We have tried to [java.util.LinkedList],
 * failed in java.util.LinkedList.remove(Object o),
 * same reason with [ArrayQueue]
 */
class CircularQueue<E>:Queue<E> {
    private var head: Node<E>? = null
    private var tail: Node<E>? = null
    override fun add(element: E): Boolean {
        val next = Node(element)
        if (head == null) {
            head = next
            tail = next
        } else {
            tail!!.next = next
            tail = next
        }
        return true
    }

    private class Node<E> constructor( var data: E) {
         var next: Node<E>? = null
    }

    override fun pollOrNull(): E? {
        val h: Node<E> = head ?: return null
        val e = h.data
        head = h.next
        if (head == null) {
            tail = null
        }
        return e
    }

    override fun peekOrNull(): E? {
        return head?.data
    }

    override fun clear() {
        head = null
        tail = null
    }

    override fun remove(element: E): Boolean {
        val h: Node<E> = head ?: return false
        if (h.data == element) {
            poll()
            return true
        }
        var prev: Node<E> = h
        var curr: Node<E>? = prev.next
        while (curr != null) {
            if (curr.data == element) {
                if (tail === curr) {
                    tail = prev
                }
                prev.next = curr.next
                return true
            } else {
                prev = curr
                curr = curr.next
            }
        }
        return false
    }

    override val size: Int
        get() = TODO("Not yet implemented")

    override fun isEmpty(): Boolean = head == null

    override fun contains(element: E): Boolean {
        val h: Node<E> = head ?: return false
        if (h.data == element) {
            return true
        }
        val prev: Node<E> = h
        var curr: Node<E>? = prev.next
        while (curr != null) {
            if (curr.data == element) {
                return true
            } else {
                curr = curr.next
            }
        }
        return false
    }

    override fun iterator(): MutableIterator<E> {
        TODO("Not yet implemented")
    }


//    fun remove(o: Any): E? {
//        val h: Node<E> = head ?: return null
//        if (h.data == o) {
//            return poll()
//        }
//        var prev: Node<E> = h
//        var curr: Node<E>? = prev.next
//        while (curr != null) {
//            if (curr.data == o) {
//                if (tail === curr) {
//                    tail = prev
//                }
//                prev.next = curr.next
//                return curr.data
//            } else {
//                prev = curr
//                curr = curr.next
//            }
//        }
//        return null
//    }
}